package com.likeycy.my.sort.cmp;

/**
 * @ClassName: InsertionSort2
 * @Description: 插入排序第二版优化
 * @Author: sodagreen
 * @Date: 2021/3/29 17:12
 * @Version: 1.0
 */
public class InsertionSort2<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int begin = 1; begin < array.length; begin++) {
            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int cur = begin;
            // 记录要插入的数据
            T tempVal = array[cur];
            while (cur > 0 && comparatorToElements(tempVal, array[cur - 1]) < 0) {
                array[cur] = array[cur - 1];
                cur--;
            }
            array[cur] = tempVal;
        }
    }
}
